package com.ma.DataStruct.trietree;

import javax.rmi.CORBA.Tie;
import java.util.Arrays;

/*
单词数组words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：

    words.length == indices.length
    助记字符串 s 以 '#' 字符结尾
    对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 '#' 字符结束（但不包括 '#'）的 子字符串 恰好与 words[i] 相等
    给你一个单词数组words ，返回成功对 words 进行编码的最小助记字符串 s 的长度 。
输入：words = ["time", "me", "bell"]
输出：10
解释：一组有效编码为 s = "time#bell#" 和 indices = [0, 2, 5] 。
    words[0] = "time" ，s 开始于 indices[0] = 0 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
    words[1] = "me" ，s 开始于 indices[1] = 2 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
    words[2] = "bell" ，s 开始于 indices[2] = 5 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
 */
public class Solution820 {
    public static void main(String[] args) {
        String[] words = {"time", "me", "bell"};
        int i = minimumLengthEncoding(words);
        System.out.println(i);

    }

    public static int minimumLengthEncoding(String[] words) {
        Trie trie = new Trie();
        Arrays.sort(words, (a, b) -> b.length() - a.length());
        int res = 0;
        for (String word : words) {
            res += trie.insert(word);
        }
        return res;
    }

    static class TrieNode {
        boolean isWord;
        TrieNode[] children;

        public TrieNode() {
            this.isWord = false;
            this.children = new TrieNode[26];
        }
    }

    static class Trie {
        TrieNode root;

        public Trie() {
            this.root = new TrieNode();
        }

        public int insert(String word) {
            TrieNode cur = root;
            boolean isNew = false;
            for (int i = word.length() - 1; i >= 0; i--) {
                int c = word.charAt(i) - 'a';
                if (cur.children[c] == null) {
                    isNew = true;
                    cur.children[c] = new TrieNode();
                }
                cur = cur.children[c];
            }
            cur.isWord = true;
            return isNew ? word.length() + 1 : 0;
        }

    }
}
